#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
    int maxProfit(vector<int> &prices)
    {
        // buy[i,0],sell[i,1],frozen[i,2]
        vector<int> dp(3, 0);
        dp[0] = -prices[0];
        dp[1] = -INT_MAX;
        dp[2] = 0;
        for (int i = 1; i < prices.size(); i++)
        {
            int buy = max(dp[0], dp[2] - prices[i]);
            int sell = dp[0] + prices[i];
            int frozen = max(dp[2], dp[1]);
            dp[0] = buy;
            dp[1] = sell;
            dp[2] = frozen;
        }
        return max(dp[1], dp[2]);
    }
};


int main()
{
    cout << "Code309" << endl;
    Solution s;
    vector<int> prices = {1, 2, 3, 0, 2};
    cout << s.maxProfit(prices) << endl;
    return 0;
}